#include <bits/stdc++.h>
using namespace std;
// O(n! * n) : 每一个元素都只有一个并且一个就有n！个排列，所以是n*n！跟全排列1一样
class Solution {
public:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int> &nums , vector<bool> &used){
		if(path.size() == nums.size()){
			result.push_back(path);
			return ;
		}
		for(int i = 0 ; i < nums.size() ; i++){
			if( i > 0 && nums[i] == nums[i-1] && used[i-1] == false ){//注意i要放在最前面不然i-1可能为负的，而i>0放在最前面可以早点掐断
				continue;
			}
			if(!used[i]){
				used[i] = true;
				path.push_back(nums[i]);
				backtracking(nums,used);
				used[i] = false;
				path.pop_back();
			}
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		result.clear();
		path.clear();
		const int N = 10;
		vector<bool> used(nums.size(),false);//注意vector如果是需要全部保持初始一致的话，这个初始化是必要的
		sort(nums.begin(),nums.end());
		backtracking(nums,used);
		return result;
	}
};
